class Solution {  //二分查找O(logn)  
public: /*根据规律，分成两区间，一区间内下标值等与下标索引的值(i==r[i])，不在该区间内,
另一区间内下标值不等与下标索引的值(i!=r[i]),该区间的最左边的值 ——》二段性
特殊处理边界情况：无缺失[0,n],数组中值与下标值都匹配(0,1、缺失值为2)，返回数组的个数*/
    int takeAttendance(vector<int>& records) {
    int n = records.size(), left = 0, right = n - 1;
    while(left < right)  //循环条件
    {
        int mid = left + (right - left) / 2;  //中点的选择(后面无+1，中点不-1)
        if(mid == records[mid]) left = mid + 1;
        else right = mid; 
    }
    if(left == records[n - 1]) return n;  //特殊处理边界情况
    return left;
    }
};


class Solution {  //方法四：哈希表，标记数组中元素是否出现O(n)
public: //数组量小且范围较集中,用数组模拟哈希,无缺失[0,n],遍历hash
    int takeAttendance(vector<int>& records) {
    int hash[10001] = {0}, n = records.size();
    for(int i = 0; i < n; i++) hash[records[i]]++;
    for(int i = 0; i < n; i++) 
    {
        if(hash[i] == 0) return i;  
    }
    return n;  
    }
};


class Solution {  //方法三：等差数列求和公式法+直接遍历数组O(n)
public:  //无缺失：元素个数n+1,第一个数0，最后一个数n
    int takeAttendance(vector<int>& records) {
    int n = records.size(), sum = 0;
    sum += ((0 + n) * (n + 1)) / 2;  
    for(int i = 0; i < n; i++)
    {
        sum -= records[i];
    }
    return sum;
    }
};

class Solution {  //方法二：直接遍历数组O(n)
public:  /*特点：无缺失，下标与下标索引的值相等
两种情况：缺失值在数组中最后一个数的 1.前面某个位置(第一、中减)，缺失值为下标值(第一个下标与数组值不等)、
                                  2.后面外置，即：缺失值为数组的长度(下标值与数组值都匹配)*/
    int takeAttendance(vector<int>& records) {
    int n = records.size();
    for(int i = 0; i < n; i++) 
    {
        if(records[i] != i) return i;  //情况1
    }
    return n;  //情况2
    }
};


class Solution { //特点：size为最大的学号,实际上所有同学的学号[0,size],实际同学总数为size+1
public:   //方法1：位运算，异或^(相同为0，相异为1)  O(n)
    int takeAttendance(vector<int>& records) {
    int n = records.size(), x = 0;  
    for(int i = 1; i <= n; i++) x ^= i; //所有同学的学号(无缺习)
    for(int i = 0; i < n; i++) x ^= records[i]; 
    return x; 
    }
};